package Algorithm.LinkedListProblem;

import java.util.Stack;

/**
 * @Author cj
 * @Date 2021/12/29 20:08
 */
public class reverseKNodes {

    static class Node {
        public int value;
        public Node next;

        public Node(int val) {
            this.value = val;
        }
    }

    // 空间复杂度：O(N)
    public static Node reverseKNodes1(Node head, int K) {
        if (K < 2) {
            return head;
        }
        Stack<Node> stack = new Stack<>();
        // pre每次调整完的最后一个；next用来记录下一段第一个
        Node newHead = head, pre = null, cur = head, next = null;
        while (cur != null) {
            next = cur.next;
            stack.push(cur);
            if (stack.size() == K) {
                pre = resign1(stack, pre, next);
                newHead = newHead == head ? cur : newHead;
            }
            cur = next;
        }
        return newHead;
    }

    public static Node resign1(Stack<Node> stack, Node left, Node right) {
        Node cur = stack.pop();
        if (left != null) {
            left.next = cur;
        }
        Node next = null;
        while (!stack.isEmpty()) {
            next = stack.pop();
            cur.next = next;
            cur = next;
        }
        // 与下一段第一个相接
        cur.next = right;
        return cur;
    }

    // 空间复杂度：O(1) 没写完，留着写
    public static Node reverseKNodes2(Node head, int K) {
        if (K < 2) {
            return head;
        }
        Node cur = head, start = null, pre = null, next = null;
        int num = 1;
        while (cur != null) {
            next = cur.next;
            if (num == K) {
                start = pre == null ? head : pre.next;
                head = pre == null ? cur : head;
                resign2(pre, start, cur, next);
                pre = start;
                num = 0;
            }
            num++;
            cur = next;
        }
        return head;
    }

    public static void resign2(Node left, Node start, Node end, Node right) {
        Node pre = start, cur = start.next, next = null;
        while (cur != right) {
            next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        if (left != null) {
            left.next = end; // 将上一段最后一个与本次调整后的第一个相连
        }
        start.next = right; // 本次调整后的最后一个节点与下一段第一个节点相连
    }

    public static void main(String[] args) {
        Node head = new Node(1);
        head.next = new Node(2);
        head.next.next = new Node(3);
        head.next.next.next = new Node(4);
        head.next.next.next.next = new Node(5);
        head.next.next.next.next.next = new Node(6);
        head.next.next.next.next.next.next = new Node(7);
        head.next.next.next.next.next.next.next = new Node(8);
        head.next.next.next.next.next.next.next.next = new Node(9);
        Node a = reverseKNodes2(head, 3);
        while (a != null) {
            System.out.println(a.value);
            a = a.next;
        }
    }
}
